package oct2013;

public class ImplementstrStr {
	int[] next;

	public String strStr(String S, String T) {
		int n = S.length();
		int m = T.length();
		if (m == 0)
			return S;
		next = new int[m];
		getNext(T);
		int i = 0, j = 0;
		while (n - i >= m - j) {
			if (j == m)
				return S.substring(i - m);
			if (j == -1 || S.charAt(i) == T.charAt(j)) {
				i++;
				j++;
			} else {
				j = next[j];
			}
		}
		return null;
	}

	void getNext(String T) {
		int n = T.length();
		int i = 1, j = -1;
		next[0] = -1;
		while (i < n) {
			if (j == -1 || T.charAt(i - 1) == T.charAt(j)) {
				next[i++] = ++j;
			} else {
				j = next[j];
			}
		}
	}
}
